import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    /**
     * 将特殊二进制字符串转换为字典序最大的特殊二进制字符串
     * 特殊二进制字符串满足：0和1的数量相等，且每个前缀中1的数量不少于0的数量
     *
     * @param s 给定的特殊二进制字符串
     * @return 字典序最大的特殊二进制字符串
     */
    public String makeLargestSpecial(String s) {
        // 基础情况：长度为0或2时直接返回（最小特殊字符串是"10"）
        if (s.length() <= 2) {
            return s;
        }

        int cnt = 0, left = 0;
        List<String> subs = new ArrayList<String>();

        // 遍历字符串，寻找平衡的特殊子串
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '1') {
                ++cnt;  // 遇到1，计数器加1
            } else {
                --cnt;  // 遇到0，计数器减1
                // 当计数器为0时，找到了一个平衡的特殊子串
                if (cnt == 0) {
                    // 递归处理子串内部部分，并构建新的特殊字符串
                    subs.add("1" + makeLargestSpecial(s.substring(left + 1, i)) + "0");
                    left = i + 1;  // 更新左指针
                }
            }
        }

        // 将所有特殊子串按字典序降序排列
        Collections.sort(subs, (a, b) -> b.compareTo(a));

        // 拼接所有子串得到最终结果
        StringBuilder ans = new StringBuilder();
        for (String sub : subs) {
            ans.append(sub);
        }
        return ans.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] testCases = {
                "11011000",          // 基本用例，应输出 "11100100"
                "10",                // 最小特殊字符串，应输出 "10"
                "111000",            // 应输出 "111000"
                "111000101000",      // 复杂用例，应输出 "111010001000"
                "101010",            // 应输出 "101010"（已经是最大）
        };
        for (String testCase : testCases) {
            String result = solution.makeLargestSpecial(testCase);
            System.out.println("输入: " + testCase);
            System.out.println("输出: " + result);
            System.out.println("--------------------");
        }
    }
}